package recursion

func GetLCSE(a, b string) int {
	if len(a) == 0 || len(b) == 0 {return 0}
	return GetLCSEProcess(a, b, len(a)-1, len(b)-1)
}

// 该方法有错误，参考traning_camp003 下对应的该题
func GetLCSEProcess(a, b string, aEnd, bEnd int) int {
	if aEnd < 0 || bEnd < 0 {return 0}
	if aEnd == len(a)-1 && bEnd == 0 {
		if a[aEnd] == b[bEnd] {return 1}
		return 0
	}
	if bEnd == len(b)-1 && aEnd == 0 {
		if b[bEnd] == a[aEnd] {return 1}
		return 0
	}
	var ans int
  	// 两个字符串的最后一个字符串都不属于公共子序列的可能性
	p1 := GetLCSEProcess(a, b, aEnd-1, bEnd)   // 最长公共字符串包含b字符串的可能性
	p2 := GetLCSEProcess(a, b, aEnd, bEnd-1)   // 最长公共字符串包含a字符串的可能性
	ans = Max(p1, p2)
	if a[aEnd] == b[bEnd] {
		return Max(ans, GetLCSEProcess(a, b, aEnd-1, bEnd-1)+1)
	} else {
		return Max(ans, GetLCSEProcess(a, b, aEnd-1, bEnd-1))
	}
}

func GetLCSEDp(a, b string) int {
	dp := make([][]int, len(a))
	for i:=0; i<len(a); i++ {
		dp[i] = make([]int, len(b))
	}
	// 设置初值
	for i:=0; i<len(a); i++ {
		if b[0] == a[i] {
			dp[i][0] = 1
		}
		if i > 0 {
			dp[i][0] = max(dp[i-1][0], dp[i][0])
		}
	}
	for i:=0; i<len(b); i++ {
		if a[0] == b[i] {
			dp[0][i] = 1
		}
		if i > 0 {
			dp[0][i] = max(dp[0][i-1], dp[0][i])
		}
	}

	for i:=1; i<len(a); i++ {
		for j:=1; j<len(b); j++ {
			dp[i][j] = Max(dp[i-1][j], dp[i][j-1])
			if a[i] == b[j] {
				dp[i][j] = Max(dp[i][j], dp[i-1][j-1]+1)
			}
		}
	}
	return dp[len(a)-1][len(b)-1]
}